# -*- coding: utf-8 -*-

import pygame
import random
import event
import os

from sprite import Model

def get_unit_list_in_range(unit_list, position, radius):
    unit_list_in_range = []

    for u in unit_list:
        # TODO: Dont hardcode this condition here
        if u.alive == False: continue

        distance = u.position.get_distance(position)
        if distance <= radius:
            unit_list_in_range.append(u)

    return unit_list_in_range

class Unit(object):
    """
    ANIM_IDLE = 0
    ANIM_MOVE = 1
    ANIM_HIT = 2
    ANIM_DEATH = 3
    ANIM_ATTACK = 4
    """

    MONSTER_MELEE = 0
    MONSTER_RANGE = 1

    def __init__(self, x=0, y=0):
        self.render_option = RenderOption()
        self.render_option.debug = False

        self.color = pygame.Color(0, 255, 0)


        self.speed = 0.1

        # Simple Vehicle Model
        self.mass = 1
        self.velocity = Vec2d(0, 0)
        self.max_speed = 0.15
        self.max_speed_sqrd = self.max_speed ** 2
        # self.max_force = 0.005
        self.max_force = self.max_speed / 5
        self.max_force_sqrd = self.max_force ** 2
        self.forward = Vec2d(0, -1)
        self.side = self.forward.perpendicular_normal()

        # Steering Variables
        self.obstacle_projection = [Vec2d(0, 0), Vec2d(0, 0), Vec2d(0, 0), Vec2d(0, 0)]
        self.obstacle_incoming = []
        self.obstacle_avoid_path = Vec2d(0, 0)

        self.search_tile = self.obstacle_projection
        self.search_tile_lines = []
        self.plane_lines = []

        self.steering_direction = Vec2d(0, 0)
        self.path_follow_line = Vec2d(0, 0)

        self.path_follow_projection_point = Vec2d(0, 0)

        # positions
        self.position = Vec2d(x, y)
        self.destination = self.position
        self.position_rect = pygame.Rect(0, 0, 32, 32)
        self.position_rect.center = self.position
        self.path = []

        # Combat stat
        self.target = None
        self.alive = True

        self.name = "Unit"
        self.hp = 100.0
        self.max_hp = 100.0
        self.attack_power = 5.0
        self.attack_speed = 1.4  # how many attack per second
        self.attack_cooldown = 0;  # how long more for next attack
        self.attack_swing_delay = 200  # delay for each attack (Can't move when attacking)

        self.experience = 0
        self.level = 1
        self.kill = 0
        self.team = 0
        self.swing_delay = 0
        self.range = 400

        self.size = 16

        # TODO: Should render on map level not Unit
        self.floating_text = []

        self.model = None

        # for AI
        self.next_decision = random.randint(1000, 2000)
        self.type = Unit.MONSTER_MELEE

    def set_color(self, color):
        self.color = color

    def get_pos_rect(self):
        return self.position_rect

    def update_kill(self, victim):
        self.kill += 1
        self.experience += 1

        # level up!
        if self.experience >= (20):
            self.level_up()

    def level_up(self):
        self.level += 1
        self.experience = 0

        self.attack_power += 1
        self.max_hp += 10
        self.hp = self.max_hp

    def damage(self, target, damage):
        Map.event.damage_source = self
        Map.event.damage_target = target
        Map.event.damage_amount = damage
        Map.event.handle(event.EventType.UNIT_DAMAGE)

    # check and update attack cooldown, then return status
    def attack(self):
        # attack cooldown
        if self.attack_cooldown <= 0:
            self.attack_cooldown += (1000 / self.attack_speed)
            self.swing_delay = self.attack_swing_delay
            self.model.set_animation(Model.ANIM_ATTACK)
            return True
        else:
            return False

    def death(self, killer):
        self.hp = 0
        self.alive = False
        self.model.set_animation(Model.ANIM_DEATH)

        if killer:
            killer.update_kill(self)


    def shoot(self, pos):
        if self.attack():
            # calculates the projectile range / destination
            direction = pos - self.position

            # create the projectile
            projectile = Projectile()
            projectile.position = self.position
            projectile.direction = direction.normalized()
            projectile.damage = self.attack_power / 2  # shoot dmg is lower
            projectile.owner = self
            return projectile

    def find_path(self, destination):
        # Temp optimization: Reject repeatative finding path that are too near
        distance_sqrd = self.destination.get_dist_sqrd(destination)
        if distance_sqrd < 256:
            #self.destination = destination
            return

        # TODO : Dont use tile coordinates for pathfinding
        start = self.position / 16
        start = (int(start.x), int(start.y))
        goal = destination / 16
        goal = (int(goal.x), int(goal.y))
        path = False

        cluster_start = self.position / 80
        cluster_start = (int(cluster_start.x), int(cluster_start.y))

        cluster_end = destination / 80
        cluster_end = (int(cluster_end.x), int(cluster_end.y))

        if cluster_start not in Map.game_map.entrance_point:
            self.destination = destination
            self.path = []
            return

        if cluster_end not in Map.game_map.entrance_point:
            self.destination = destination
            self.path = []
            return


        if cluster_start == cluster_end:
            cluster_pathnode = Map.game_map.cluster_pathnode[cluster_start]
            path = Pathfinder.a_star(start, goal, cluster_pathnode)

        # Still not able to find the path, use hpa to find
        if path == False:
            # print (cluster_start,cluster_end)
            # print Map.game_map.entrance_point[cluster_start]
            # print Map.game_map.entrance_point[cluster_end]

            pathnode = Map.game_map.pathnode

            cluster_pathnode = Map.game_map.cluster_pathnode[cluster_start]
            for e in Map.game_map.entrance_point[cluster_start]:
                temp_path = Pathfinder.a_star(start, e, cluster_pathnode)
                if temp_path:
                    pathnode.add(start, e)
                    pathnode.set_edge_value(start, e, temp_path)

            cluster_pathnode = Map.game_map.cluster_pathnode[cluster_end]
            for e in Map.game_map.entrance_point[cluster_end]:
                temp_path = Pathfinder.a_star(e, goal, cluster_pathnode)
                if temp_path:
                    pathnode.add(e, goal)
                    pathnode.set_edge_value(e, goal, temp_path)

            abs_path = Pathfinder.haa_star(start, goal)

            if abs_path:
                path = []
                for i in xrange(len(abs_path) - 1):
                    p = pathnode.get_edge_value(abs_path[i], abs_path[i + 1])

                    if p:
                        last = len(path) - 1
                        if last >= 0 and path[last] == p[0]:
                            path.pop()

                        path += p


            for e in Map.game_map.entrance_point[cluster_start]:
                pathnode.delete(start, e)

            for e in Map.game_map.entrance_point[cluster_end]:
                pathnode.delete(e, goal)

        if path:
            self.path = []
            # remove nodes that are for tile alignment
            path.remove(path[0])
            if len(path) > 0: path.pop()

            for p in path:
                v = Vec2d(p)
                v = v + 1
                v *= 16
                self.path.append(v)

            self.path.append(destination)
            self.destination = destination
            self.path_smoothing()
        else:
            self.path = []
            self.destination = destination

    def path_smoothing(self):
        self.obstacle_incoming = []
        self.search_tile_lines = []
        if not self.path:
            return

        #print "base path %s" % (self.path)
        prev = self.path[0]
        current = None
        bounding_size = self.size
        wall_check_size_sqrd = (self.size ** 2) + 2 * (16 ** 2) + 2

        new_path = self.path[:]

        # Check P -> C -> N by skpping C
        # If skipping C hit a wall, assign P to C and continue to scan
        # Else we can remove C and keep going
        # First node and last node should always be there
        for x in xrange(0, len(self.path) - 1):
            current = self.path[x]
            next_node = self.path[x + 1]

            #print "scanning: %s -> %s" % (next_node, prev)

            forward = next_node - prev
            side = forward.perpendicular_normal()

            # Project a rectangle to hit the wall
            left_side = side * -bounding_size + prev
            right_side = side * bounding_size + prev
            left_forward = forward + left_side
            right_forward = forward + right_side

            # Wall detection
            l = min(left_side.x, right_side.x, right_forward.x, left_forward.x)
            r = max(left_side.x, right_side.x, right_forward.x, left_forward.x)
            u = min(left_side.y, right_side.y, right_forward.y, left_forward.y)
            d = max(left_side.y, right_side.y, right_forward.y, left_forward.y)

            rect = pygame.Rect(l, u, (r - l), (d - u))
            #pygame.draw.rect(Map.game_map.grid_overlay, (255, 0, 0), rect, 2)

            pathmap = Map.game_map.get_pathmap_in_rect(rect)

            wall_detected = False
            #Check for wall
            for tile_point in pathmap:
                (x, y) = tile_point
                x = x * 16 + 8
                y = y * 16 + 8
                tile_point = Vec2d(x, y)

                p2 = Map.point_line_perpendicular_base(tile_point, prev, side)
                if prev.get_dist_sqrd(p2) <= wall_check_size_sqrd:
                    #print "wall projected, do not remove %s" % (current)
                    prev = current
                    wall_detected = True
                    break

            if not wall_detected:
                #print "removing %s" % (current)
                new_path.remove(current)

        self.path = new_path
        #print "end path %s" % (self.path)
        return

    def update(self, duration):
        # update floating text first
        for ft in self.floating_text:
            ft.update(duration)
            if ft.active == False:
                self.floating_text.remove(ft)

        # update model animation
        self.model.update(duration)
        forward_angle = self.forward.get_angle()
        self.model.set_direction(forward_angle)

        if self.alive == False:
            return

        if self.attack_cooldown <= 0:
            if self.velocity.get_length_sqrd() <= 0.0001:
                if self.model._animation != Model.ANIM_IDLE:
                    self.model.set_animation(Model.ANIM_IDLE)
            elif self.model._animation != Model.ANIM_MOVE:
                self.model.set_animation(Model.ANIM_MOVE)

        # Update combat
        duration = self.update_combat(duration)
        if duration <= 0:
            # Do not continue: Combat used up all duration
            return

        displacement = self.update_movement(duration)
        future_position = self.position + displacement

        if displacement > 0:
            # Collision check
            # TODO: Incomplete and need refactor
            # http://stackoverflow.com/questions/6459035/2d-collision-response-between-circles
            for u in Map.all_unit:
                if u == self:
                    continue

                if not u.alive:
                    continue

                #dlen = d.get_length()
                d_len_sqrd = future_position.get_dist_sqrd(u.position)

                min_distance_sqrd = (self.size * 2 - 4) ** 2

                if d_len_sqrd < min_distance_sqrd:
                    # t = (dlen - min_distance) / displacement.get_length()
                    # future_position = self.position + (displacement * t)

                    # cancel future movement
                    future_position = self.position

            # Map collision check
            if Map.game_map.collide(future_position, self.size):
                future_position = self.position

            self.position = future_position

            self.position_rect.center = self.position


        # simple bounding check
        # TODO: dont hardcode hack
        x_bound = Map.game_map.map_size.x
        y_bound = Map.game_map.map_size.y
        current_pos = self.position_rect.center
        if self.position_rect.left < 0:
            self.position_rect.left = 0
        if self.position_rect.right > x_bound:
            self.position_rect.right = x_bound
        if self.position_rect.top < 0:
            self.position_rect.top = 0
        if self.position_rect.bottom > y_bound:
            self.position_rect.bottom = y_bound

        if current_pos != self.position_rect.center:
            self.position = Vec2d(self.position_rect.center)



    def update_combat(self, duration):
        # update attack cooldown
        self.attack_cooldown -= duration

        if self.target and self.target.alive:
            # check distance
            target_distance = self.position - self.target.position
            target_distance = target_distance.length

            # attack!
            if target_distance < 50:
                while self.attack():
                    self.damage(self.target, self.attack_power)

                # reset target & destination after attack
                self.target = None
                self.destination = self.position
                self.path = []

                return 0

        # reset cooldown to 0 if too low
        if self.attack_cooldown < 0:
            self.attack_cooldown = 0

        # swing delay
        if duration <= self.swing_delay:
            self.swing_delay -= duration
            return 0
        else:
            self.swing_delay = 0
            duration -= self.swing_delay

        # return remaining duration for movement
        return duration

    def update_movement(self, duration):
        # the actual movement
        # seek
        steering_force = Vec2d(0, 0)
        steering_weight_total = 0

        # wall avoiding
        wall_avoidance = self.steering_wall_avoidance()
        if wall_avoidance:
            steering_weight = 1
            steering_force += wall_avoidance * steering_weight
            steering_weight_total += steering_weight

        # obstacle avoiding
        obstacle_avoidance = self.steering_obstacle_avoidance()
        #obstacle_avoidance = False
        if obstacle_avoidance:
            steering_weight = 2
            steering_force += obstacle_avoidance * steering_weight
            steering_weight_total += steering_weight

        # path following
        path_following = self.steering_path_follow()
        if path_following:
            steering_weight = 1
            steering_force += path_following * steering_weight
            steering_weight_total += steering_weight

            if self.velocity.get_length_sqrd() == 0:
                self.model.set_animation(Model.ANIM_MOVE)

        if steering_weight_total:
            # Average
            # TODO: Decision based steering instead of weighted average
            steering_force = steering_force / steering_weight_total

            # TODO: Make a truncate function
            # steering_force = truncate(self.steering_direction, self.max_force)
            if steering_force.get_length_sqrd() > self.max_force_sqrd:
                steering_force = steering_force.normalized() * self.max_force

            acceleration = steering_force / self.mass
            self.velocity = self.velocity + acceleration
            speed_sqrd = self.velocity.get_length_sqrd()

            if speed_sqrd > self.max_speed_sqrd:
                self.velocity = self.velocity.normalized() * self.max_speed

            if speed_sqrd > 0:
                self.forward = self.velocity.normalized()
                self.side = self.forward.perpendicular_normal()

        displacement = self.velocity * duration
        return displacement

    def steering_path_follow(self):
        project_length = 50
        path_radius = 2
        path_radius_sqrd = path_radius ** 2

        # Easy arrival fix
        # TODO: Really? Use this or actually fixing the arrival behavior?
        if self.position.get_dist_sqrd(self.destination) < 1:
            self.velocity = Vec2d(0, 0)
            return None


        # Consider path node that are too close as reached
        for p in self.path[:]:
            distance_sqrd = self.position.get_dist_sqrd(p)

            if distance_sqrd < path_radius_sqrd:
                self.path.remove(p)
            else:
                break


        if len(self.path) > 0:
            nearest_point = self.path[0]

            # TODO 2: This is breaking the path smoothing algorithm now
            """
            projection_point = (self.forward * project_length) + self.position
            projection_point = self.position

            min_distance = None
            nearest_point = None
            for p in self.path:
                distance_sqrd = projection_point.get_dist_sqrd(p)

                # Check for nearest point
                if min_distance == None or distance_sqrd < min_distance:
                    min_distance = distance_sqrd
                    nearest_point = p

            # Clean up "old" path that are out of projection range
            # This is a temp solution to overshooting previous path node
            # TODO: Review this


            if nearest_point:
                for p in self.path[:]:
                    if p != nearest_point:
                        self.path.remove(p)
                    else:
                        break
            """

            if nearest_point:  # and min_distance > path_radius:
                # seek nearest_point
                direction = nearest_point - self.position
                direction = direction.normalized()
                desired_velocity = self.max_speed * direction
                steering_force = desired_velocity - self.velocity

            self.path_follow_projection_point = (int(nearest_point.x), int(nearest_point.y))

        # No more path, use arrival behavior
        else:
            # arrival
            target_offset = self.destination - self.position
            distance = target_offset.get_length()

            if distance > 0:
                slowing_distance = 0.5
                ramped_speed = self.max_speed * (distance / slowing_distance)
                clipped_speed = min(ramped_speed, self.max_speed)
                desired_velocity = (clipped_speed / distance) * target_offset.normalized()
                steering_force = desired_velocity - self.velocity
            else:
                return None

        self.path_follow_line = steering_force
        return steering_force

    def steering_obstacle_avoidance(self):
        return
        self.obstacle_incoming = []

        project_length = 50
        bounding_size = self.size

        left_side = self.side * -bounding_size + self.position
        right_side = self.side * bounding_size + self.position
        left_forward = self.forward * project_length + left_side
        right_forward = self.forward * project_length + right_side

        self.obstacle_projection = [left_side, right_side, right_forward, left_forward]

        scan_range_sqrd = (project_length + bounding_size) ** 2
        for u in Map.all_unit:
            if u == self:
                continue

            if not u.alive:
                continue

            circle = (u.position, u.size)
            if self.position.get_dist_sqrd(u.position) < scan_range_sqrd:
                if Map.circle_rect_intersect(circle, self.obstacle_projection):
                    self.obstacle_incoming.append(u.position)

        nearest_obstacle = None
        if len(self.obstacle_incoming) >= 1:
            nearest_obstacle = (
                Map.get_nearest_point(self.obstacle_incoming, self.position)
            )

        if nearest_obstacle:
            if nearest_obstacle.dot(self.side) >= 0:
                self.obstacle_avoid_path = self.max_speed * self.side
            else:
                self.obstacle_avoid_path = self.max_speed * -self.side

        else:
            return False

        steering_force = self.obstacle_avoid_path
        return steering_force

    def steering_wall_avoidance(self):
        # Wall detection from where on
        future_position = self.position + self.velocity
        l = future_position.x - 16
        r = future_position.x + 16
        u = future_position.y - 16
        d = future_position.y + 16

        rect = pygame.Rect(l, u, (r - l), (d - u))

        self.search_tile = [(l, u), (r, u), (r, d), (l, d)]

        pathmap = Map.game_map.get_pathmap_in_rect(rect)

        self.obstacle_incoming = []
        min_distance_sqrd = 24 ** 2
        for p in pathmap:
            (x, y) = p
            x = x * 16 + 8
            y = y * 16 + 8
            p = Vec2d(x, y)
            #p2 = Map.point_line_perpendicular_base(p, self.position, self.side)

            if self.position.get_dist_sqrd(p) < min_distance_sqrd:
                self.obstacle_incoming.append(p)

        nearest_obstacle = None
        if len(self.obstacle_incoming) >= 1:
            nearest_obstacle = (
                Map.get_nearest_point(self.obstacle_incoming, self.position)
            )

        if nearest_obstacle:
                steering_force = nearest_obstacle - self.position
                angle = steering_force.get_angle()

                # bias each corner to one side
                new_angle = (2 + math.ceil((angle - 45) / 90)) * 90
                steering_force.angle = new_angle
                steering_force = steering_force.normalized()

        else:
            return False

        return steering_force

    def render(self, target):
        radius = self.size

        pos = (int(self.position.x), int(self.position.y))
        pygame.draw.circle(target, self.color, pos, radius + 2 , 2)

        self.model.render(target, pos)

        if self.render_option.debug:
            self.render_path(target)
            self.render_steering_info(target)

        self.render_floating_text(target)


    def render_path(self, target):
        if self.path:
            pygame.draw.line(target, self.color, self.position, self.path[0], 3)

            if len(self.path) > 1:
                pygame.draw.lines(target, self.color, False, self.path, 3)

    def render_occupied_pathmap(self, target):
        return False

    def render_steering_info(self, target):
        # Draw a circle border to highlight incoming obstacle
        for p in Map.player.obstacle_incoming:
            (x, y) = (int(p[0]), int(p[1]))
            pygame.draw.circle(target, (255, 0, 0), (x, y), 2)

        # Draw the steering projection box
        rect = pygame.draw.polygon(target, (255, 255, 255), self.obstacle_projection, 1)

        # Draw projectle tiles info
        pygame.draw.polygon(target, (0, 255, 255), self.search_tile, 1)

        for line in self.search_tile_lines:
            pygame.draw.line(target, (0, 255, 255), line[0], line[1], 1)

        temp = []
        for v in self.obstacle_projection:
            temp.append(v - rect.topleft)

        projection_fill = pygame.Surface(rect.size, pygame.SRCALPHA, 32)
        # projection_fill.set_alpha(192)
        pygame.draw.polygon(projection_fill, (255, 255, 128, 192), temp, 0)
        target.blit(projection_fill, (rect.topleft))

        # Draw Velocity Line
        velocity_end = self.position + (self.velocity * 200)
        pygame.draw.line(target, (255, 0, 0), self.position, velocity_end, 2)

        # Draw Forward Line
        forward_end = self.position + (self.forward * self.size)
        pygame.draw.line(target, (255, 255, 255), self.position, forward_end, 2)

        # Draw Steering Line
        # steering_end = self.position + (self.steering_direction * 400)
        # pygame.draw.line(target, (0, 128, 0), self.position, steering_end, 2)

        # path_follow = self.position + (self.path_follow_line * 400)
        # pygame.draw.line(target, (0, 0, 128), self.position, path_follow, 2)

        obstacle_avoid = self.position + (self.obstacle_avoid_path * 50)
        pygame.draw.line(target, (128, 0, 128), self.position, obstacle_avoid, 2)

        if self.path_follow_projection_point:
            pygame.draw.circle(target, (0, 0, 255), self.path_follow_projection_point, 3)

    def render_floating_text(self, target):
        for ft in self.floating_text:
            (x, y) = self.position_rect.topleft
            y += ft.y_offset
            target.blit(ft.surface, (x, y))


class Projectile(object):

    def __init__(self):
        self.position = Vec2d(0, 0)
        # self.destination = Vec2d(0,0)
        # self.direction = Vec2d(0,0)
        self.lifetime = 400

        self.speed = 1

        self.damage = 0
        self.owner = None

        self.alive = True

        self.remove_on_hit = True

        self.collide_unit = True

        # keep a list of hitten targets
        self.hitten_list = []

    def set_destination(self, destination):
        direction = destination - self.position
        distance = direction.get_length()

        self.set_range(distance)
        self.direction = direction.normalized()

    def set_range(self, distance):
        # convert range to lifetime
        self.lifetime = distance / self.speed

    def update(self, duration):
        if self.alive == False:
            return

        # check if lifetime is shorter than duration
        if self.lifetime < duration:
            duration = self.lifetime

        # the actual movement
        displacement = (self.speed * duration)
        self.position = self.position + (displacement * self.direction)

        if self.collide_unit:
            for unit in Map.all_unit:
                # TODO: Projectile may be flying too far per frame
                # Need some kind of line collision instead of point
                if unit.get_pos_rect().collidepoint(self.position):
                    Map.event.projectile = self
                    Map.event.projectile_target = unit
                    Map.event.handle(event.EventType.PROJECTILE_HIT)

        self.lifetime -= duration
        if self.lifetime <= 0:
            self.alive = False
            Map.event.projectile = self
            Map.event.handle(event.EventType.PROJECTILE_DEATH)


    def render(self, target):
        x = int(self.position.x)
        y = int(self.position.y)
        pygame.draw.circle(target, (255, 0, 0), (x, y) , 6)

# Chain Projectile
class Chain(Projectile):
    def __init__(self):
        Projectile.__init__(self)

        self.speed = 1.5
        self.jump = 4
        self.jump_distance = 200

        self.jump_point = []

    def render(self, target):
        if len(self.jump_point) == 0:
            self.jump_point.append(Vec2d(self.position))

        # line_end = self.position + (self.direction * 20)
        prev_position = self.jump_point[0]
        for i in range(1, len(self.jump_point)):
            next_position = self.jump_point[i]
            pygame.draw.line(target, (0, 255, 255), prev_position, next_position, 6)
            prev_position = next_position

        pygame.draw.line(target, (0, 255, 255), prev_position, self.position, 6)

# Fireball Projectile
class ProjectileFireball(Projectile):
    def __init__(self):
        Projectile.__init__(self)
        self.collide_unit = False

    def render(self, target):
        x = int(self.position.x)
        y = int(self.position.y)
        pygame.draw.circle(target, (255, 255, 0), (x, y) , 10)


class SfxFireball(object):
    def __init__(self):
        self.lifetime = 250
        self.start_radius = 5
        self.end_radius = 100
        self.radius = 5
        self.speed = 0.4
        self.alive = True

        self.position = None

    def update(self, duration):
        if self.alive == False:
            return

        # check if lifetime is shorter than duration
        if self.lifetime < duration:
            duration = self.lifetime

        self.radius += duration * self.speed
        self.lifetime -= duration
        if self.lifetime <= 0:
            self.alive = False


    def render(self, target):
        x = int(self.position.x)
        y = int(self.position.y)
        radius = int(self.radius)
        pygame.draw.circle(target, (255, 255, 0), (x, y) , radius, 0)

class SfxFireballBurning(object):
    def __init__(self):
        self.alive = True
        self.position = None

    def update(self, duration):
        pass

    def render(self, target):
        base_x = int(self.position.x)
        base_y = int(self.position.y)

        # TODO: Particle effect
        for i in xrange(1, 10):
            x = base_x + random.randint(-16, 16)
            y = base_y + random.randint(-16, 16)
            pygame.draw.circle(target, (255, 255, 0), (x, y) , 1)



"""
Skill trigger Steps
1. trigger skill cast (keyinput, AI, other trigger)
2. handle skill cast action
3. generate skill effect (if any)
4. on-going effect
5. end of skill effect


Skill samples
1. direct dmg / heal
2. add a buff
3. affect unit movement (push or pull or teleport)
4. fire a projectile, damage / heal / whatever on hit
5.
"""
class Heal(object):
    def __init__(self):
        self.value = 20

    def cast(self, source, target):
        # do something on precast


        # since this is an instant skill, effect casted immediately
        Map.event.heal_source = source
        Map.event.heal_target = target
        Map.event.heal_amount = self.value
        Map.event.handle(event.EventType.UNIT_HEAL)

class Fireball(object):
    def __init__(self):
        self.value = 10
        self.radius = 100
        self.effect_list = []
        self.owner = None

    def cast(self, source, destination):
        # do something on precast


        # create fireball projectile
        projectile = ProjectileFireball()
        projectile.position = source.position
        projectile.owner = self
        projectile.set_destination(destination)
        self.effect_list.append(projectile)
        Map.projectile_list.append(projectile)


class BuffDamageOverTime(object):
    def __init__(self):
        self.tick = 500
        self.tick_cooldown = 0

        self.owner = None
        self.target = None
        self.damage = 1.0
        self.duration = 3000

        self.alive = True

        self.sfx = SfxFireballBurning()

        Map.effect_list.append(self.sfx)

    def update(self, duration):
        self.tick_cooldown -= duration
        self.sfx.position = self.target.position

        if not self.alive:
            return

        if not self.target.alive:
            self.alive = False
            self.sfx.alive = False
            return


        if self.tick_cooldown <= 0:
            self.tick_cooldown += self.tick
            self.owner.damage(self.target, self.damage)

        self.duration -= duration
        if self.duration <= 0:
            self.alive = False
            self.sfx.alive = False


class FloatingText(object):


    def __init__(self, text, pos, lifetime=500):
        self.text = text
        self.position = pos
        self.life = lifetime

        font = pygame.font.Font(pygame.font.get_default_font(), 18)
        self.surface = font.render(self.text, 1, (255, 255, 0))

        self.y_offset = 0
        self.y_speed = 0.2

        self.active = True

    def update(self, duration):
        self.y_offset -= self.y_speed * duration
        self.life -= duration
        if self.life <= 0: self.active = False

    # def render(self, target)

    def set_color(self, color):
        font = pygame.font.Font(pygame.font.get_default_font(), 18)
        self.surface = font.render(self.text, 1, color)


class Map(object):
    def __init__(self, filename):
        from pytmx import tmxloader
        self.tiledmap = tmxloader.load_pygame(filename, pixelalpha=True)
        self.focus = Vec2d(0, 0)
        self.view_port_size = Vec2d(1024, 768)
        self.offset = Vec2d(0, 0)
        self.layer_surface = []

        self.map_size = Vec2d(
                        self.tiledmap.width * self.tiledmap.tilewidth,
                        self.tiledmap.height * self.tiledmap.tileheight
                        )

        self.pathmap = dict()
        self.base_clearance = dict()
        self.clearance = dict()
        self.pathmap_overlay = None

        self.pathnode = PathGraph()

        self.path_overlay = None

        self.grid_overlay = None

        self.clearance_overlay = None

        self.last_get_pathmap = None

        self.closedset = None
        self.map_collide_offender = None

        self.prerender_map()
        self.generate_pathmap()
        self.generate_grid_overlay()

        # Render Option
        self.render_option = RenderOption()
        self.render_option.debug = False

        self.collision_line = False

        self.resource_manager = ResourceManager()

    def set_focus(self, pos):
        self.focus = pos

    def get_pos_from_mouse(self):
        mx, my = pygame.mouse.get_pos()
        return Vec2d(mx + self.offset.x, my + self.offset.y)

    def calculate_pathmap_clearance(self, max_size):
        self.base_clearance = dict()

        for y in xrange(0, self.tiledmap.height * 2):
            for x in xrange(0, self.tiledmap.width * 2):
                self.base_clearance[x, y] = self.calculate_clearance(x, y , max_size)

        self.clearance = self.base_clearance.copy()

    def get_pathmap_from_point(self, point):
        tx = int(point.x / (self.tiledmap.tilewidth / 2))
        ty = int(point.y / (self.tiledmap.tileheight / 2))

        pathmap = []
        for x in xrange(tx - 1, tx + 2):
            for y in xrange(ty - 1, ty + 2):
                if (x, y) in self.pathmap:
                    pathmap.append((x, y))

        return pathmap

    def collide(self, position, size):
        pw = self.tiledmap.tilewidth / 2
        ph = self.tiledmap.tileheight / 2
        px = int(position.x / (pw))
        py = int(position.y / (ph))

        size = size - 2

        for x in xrange(px - 1, px + 2):
            for y in xrange(py - 1, py + 2):
                if (x, y) in self.pathmap and not self.pathmap[(x, y)]:
                    circle = (position, size)
                    rect = pygame.Rect(x * pw, y * ph, pw, ph)
                    rectangle = (
                        Vec2d(rect.topleft),
                        Vec2d(rect.topright),
                        Vec2d(rect.bottomright),
                        Vec2d(rect.bottomleft)
                    )
                    if Map.circle_rect_intersect(circle, rectangle):
                        self.map_collide_offender = (x, y)
                        return True

        return False

    @staticmethod
    def point_line_perpendicular_base(point, point_in_line, direction):
        # http://stackoverflow.com/questions/5227373/minimal-perpendicular-vector-between-a-point-and-a-line
        P = point
        D = direction
        A = point_in_line

        return A + ((P - A).dot(D)) * D

    @staticmethod
    def circle_rect_intersect(circle, rectangle):
        # http://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection
        (p, r) = circle
        (a, b, c, d) = rectangle

        return (Map.point_in_rectangle(p, rectangle) or
            Map.circle_line_intersect(circle, (a, b)) or
            Map.circle_line_intersect(circle, (b, c)) or
            Map.circle_line_intersect(circle, (c, d)) or
            Map.circle_line_intersect(circle, (d, a)))

    @staticmethod
    def point_in_rectangle(p, rectangle):
        (a, b, c, d) = rectangle
        ap = p - a
        ab = b - a
        ad = d - a

        if 0 <= ap.dot(ab) <= ab.dot(ab) and 0 <= ap.dot(ad) <= ad.dot(ad):
            return True

        return False

    @staticmethod
    def circle_line_intersect(circle, line):
        # Source: http://stackoverflow.com/a/1084899
        (E, L) = line
        (c, r) = circle
        d = L - E
        f = E - c

        a = d.dot(d)
        b = 2 * f.dot(d)
        c = f.dot(f) - r * r

        discriminant = b * b - 4 * a * c;
        if discriminant < 0:
            return False

        else:
            # ray didn't totally miss sphere,
            # so there is a solution to
            # the equation.

            discriminant = math.sqrt(discriminant);

            # either solution may be on or off the ray so need to test both
            # t1 is always the smaller value, because BOTH discriminant and
            # a are nonnegative.
            t1 = (-b - discriminant) / (2 * a);
            t2 = (-b + discriminant) / (2 * a);

            # 3x HIT cases:
            #          -o->             --|-->  |            |  --|->
            # Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit),

            # 3x MISS cases:
            #       ->  o                     o ->              | -> |
            # FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1)

            if t1 >= 0 and t1 <= 1:
                # t1 is an intersection, and if it hits,
                # it's closer than t2 would be
                # Impale, Poke
                return True

            # here t1 didn't intersect so we are either started
            # inside the sphere or completely past it
            if t2 >= 0 and t2 <= 1:
                # ExitWound
                return True

            # no intn: FallShort, Past, CompletelyInside
            return False

    @staticmethod
    def get_nearest_unit(unit_list, pos):
        min_distance = -1
        selected = None
        for u in unit_list:
            # TODO: Dont hardcode this condition here
            if u.alive == False: continue

            distance = u.position.get_distance(pos)
            if min_distance == -1 or distance < min_distance:
                selected = u
                min_distance = distance

        return selected

    @staticmethod
    def get_nearest_point(point_list, pos):
        min_distance = -1
        selected = None
        for p in point_list:
            distance = pos.get_distance(p)
            if min_distance == -1 or distance < min_distance:
                selected = p
                min_distance = distance

        return selected

    def calculate_clearance(self, x, y, max_size):
        if self.pathmap[x, y] == 0:
            return 0

        clearance = 0

        max_x = self.tiledmap.width * 2
        max_y = self.tiledmap.height * 2

        while True:
            for tx in xrange(x, x + clearance + 1):
                for ty in xrange(y, y + clearance + 1):
                    if tx >= max_x or ty >= max_y:
                        return clearance

                    if self.pathmap[tx, ty] == 0:
                        return clearance

            clearance += 1

            if clearance >= max_size:
                return clearance

    def recalculate_clearance(self):
        self.clearance = self.base_clearance.copy()
        pw = self.tiledmap.tilewidth / 2
        ph = self.tiledmap.tileheight / 2

        for u in self.all_unit:
            if u.alive == False:
                continue

            occupied = self.get_pathmap_from_point(u.position)

            for p in occupied:
                (x, y) = p
                circle = (u.position, u.size)
                rect = pygame.Rect(x * pw, y * ph, pw, ph)
                rectangle = (
                    Vec2d(rect.topleft),
                    Vec2d(rect.topright),
                    Vec2d(rect.bottomright),
                    Vec2d(rect.bottomleft)
                )

                if Map.circle_rect_intersect(circle, rectangle):
                    if p in self.clearance:
                        self.clearance.pop(p)

                        # TODO: Dont hardcode
                        # Remap clearance of its topleft node
                        self.update_clearance_from_base((x - 1, y - 1), -1)
                        self.update_clearance_from_base((x - 1, y), -1)
                        self.update_clearance_from_base((x, y - 1), -1)

        return self.clearance

    def get_clearance(self, key):
        if key in self.base_clearance:
            return self.base_clearance[key]
        else:
            return 0

    def update_clearance_from_base(self, key, diff):
        if key in self.clearance:
            if key in self.base_clearance:
                self.clearance[key] = self.base_clearance[key] + diff
                if self.clearance[key] < 0: self.clearance[key] = 0

    def prerender_map(self):
        tw = self.tiledmap.tilewidth
        th = self.tiledmap.tileheight

        gt = self.tiledmap.getTileImage

        for l in xrange(0, len(self.tiledmap.layers)):
            self.layer_surface.insert(l, pygame.Surface(self.map_size))
            # self.layer_surface.fill((0,128,255))

            for y in xrange(0, self.tiledmap.height):
                for x in xrange(0, self.tiledmap.width):
                    tile = gt(x, y, l)
                    if tile: self.layer_surface[l].blit(tile, (x * tw, y * th))

    def generate_pathmap(self):
        # initialize pathing map
        for y in xrange(0, self.tiledmap.height):
            for x in xrange(0, self.tiledmap.width):
                gid = self.tiledmap.getTileGID(x, y, 0)

                path = (0, 0, 0, 0)

                # TODO Dont hardcode
                if gid == 10: path = (1, 1, 1, 0)
                elif gid == 11: path = (1, 1, 0, 0)
                elif gid == 16: path = (1, 0, 1, 0)
                elif gid == 18: path = (0, 1, 0, 1)
                elif gid == 26: path = (0, 0, 0, 1)
                elif gid == 27: path = (0, 1, 1, 1)
                elif gid == 29: path = (1, 0, 0, 0)
                elif gid == 35: path = (1, 0, 1, 1)
                elif gid == 36: path = (0, 0, 1, 1)
                elif gid == 37: path = (0, 0, 1, 1)
                elif gid == 38: path = (0, 1, 1, 1)

                else: path = (1, 1, 1, 1)

                if gid == 13 or gid == 14 or gid == 19 or gid == 20 or gid == 17:
                    path = (0, 0, 0, 0)

                # build pathmap
                px = x * 2
                py = y * 2

                self.pathmap[px, py] = path[0]
                self.pathmap[px + 1, py] = path[1]
                self.pathmap[px, py + 1] = path[2]
                self.pathmap[px + 1, py + 1] = path[3]

        self.calculate_pathmap_clearance(2)

        self.generate_pathmap_overlay()

    def get_pathmap_in_rect(self, rect):
        tw = self.tiledmap.tilewidth
        th = self.tiledmap.tileheight
        pw = tw / 2
        ph = th / 2

        l = rect.left / pw
        r = rect.right / pw + 1
        t = rect.top / ph
        b = rect.bottom / ph + 1

        pathmap = []
        for y in xrange(t, b):
            for x in xrange(l, r):
                if (x, y) in self.pathmap and self.pathmap[(x, y)] == 0:
                    pathmap.append((x, y))

        self.last_get_pathmap = pathmap
        return pathmap

    def generate_pathnode(self):
        # TODO: Remove all drawing function from this function
        cd = 80
        cw = int(self.map_size.x / cd)
        ch = int(self.map_size.y / cd)

        pw = self.tiledmap.tilewidth / 2
        ph = self.tiledmap.tileheight / 2

        px = cd / pw
        py = cd / ph

        self.path_overlay = pygame.Surface(self.map_size, pygame.SRCALPHA, 32)

        self.passpath = pygame.Surface((16, 16), pygame.SRCALPHA, 32)
        self.passpath.fill(pygame.Color(0, 255, 255, 128))

        self.badpath = pygame.Surface((16, 16), pygame.SRCALPHA, 32)
        self.badpath.fill(pygame.Color(128, 0, 0, 128))

        self.encpath = pygame.Surface((16, 16), pygame.SRCALPHA, 32)
        self.encpath.fill(pygame.Color(0, 255, 0, 192))

        self.entrance_point = dict()
        self.cluster_pathnode = dict()

        entrance_point = self.entrance_point
        cluster_pathnode = self.cluster_pathnode

        for x in xrange(0, cw):
            for y in xrange(0, ch):
                entrance_point[x, y] = []

                cluster_pathnode[x, y] = dict()

        for x in xrange(0, cw):
            for y in xrange(0, ch):
                # topright = ((x + 1) * cd, y * cd)
                # bottomright = ((x + 1) * cd, (y + 1) * cd)
                # bottomleft = ((x) * cd, (y + 1) * cd)

                # pygame.draw.line(self.path_overlay, (64,0,0), topright, bottomright, 4)
                # pygame.draw.line(self.path_overlay, (64,0,0), bottomleft, bottomright, 4)

                start_x = x * px
                end_x = (x + 1) * px
                start_y = y * py
                end_y = (y + 1) * py

                begin_x = None
                begin_y = None

                for xx in xrange(start_x, end_x):
                    for yy in xrange(start_y, end_y):
                        cluster_pathnode[x, y][xx, yy] = self.get_clearance((xx, yy))

                for xx in xrange(start_x, end_x):
                    self.draw_clearance_tile(xx, end_y - 1)
                    self.draw_clearance_tile(xx, end_y)

                    clearance_from = self.get_clearance((xx, end_y - 1))
                    clearance_to = self.get_clearance((xx, end_y))

                    if begin_x != None:
                        if clearance_from < 2 or clearance_to < 2:
                            begin = (begin_x, end_y - 1)
                            end = (xx - 1, end_y - 1)
                            e1 = self.insert_entrance_point(begin, end, entrance_point[x, y])

                            begin = (begin_x, end_y)
                            end = (xx - 1, end_y)
                            e2 = self.insert_entrance_point(begin, end, entrance_point[x, y + 1])
                            begin_x = None

                            self.pathnode.add(e1, e2)
                            self.pathnode.set_edge_value(e1, e2, [e1, e2])
                            self.pathnode.add(e2, e1)
                            self.pathnode.set_edge_value(e2, e1, [e2, e1])

                    else:
                        if clearance_from >= 2 and clearance_to >= 2:
                            begin_x = xx

                if begin_x != None:
                    begin = (begin_x, end_y - 1)
                    end = (xx, end_y - 1)
                    e1 = self.insert_entrance_point(begin, end, entrance_point[x, y])

                    begin = (begin_x, end_y)
                    end = (xx, end_y)
                    e2 = self.insert_entrance_point(begin, end, entrance_point[x, y + 1])
                    begin_x = None

                    self.pathnode.add(e1, e2)
                    self.pathnode.set_edge_value(e1, e2, [e1, e2])
                    self.pathnode.add(e2, e1)
                    self.pathnode.set_edge_value(e2, e1, [e2, e1])

                for yy in xrange(start_y, end_y):
                    self.draw_clearance_tile(end_x - 1, yy)
                    self.draw_clearance_tile(end_x, yy)

                    clearance_from = self.get_clearance((end_x - 1, yy))
                    clearance_to = self.get_clearance((end_x, yy))

                    if begin_y != None:
                        if clearance_from < 2 or clearance_to < 2:
                            begin = (end_x - 1, begin_y)
                            end = (end_x - 1, yy - 1)
                            e1 = self.insert_entrance_point(begin, end, entrance_point[x, y])

                            begin = (end_x, begin_y)
                            end = (end_x, yy - 1)
                            e2 = self.insert_entrance_point(begin, end, entrance_point[x + 1, y])
                            begin_y = None

                            self.pathnode.add(e1, e2)
                            self.pathnode.set_edge_value(e1, e2, [e1, e2])
                            self.pathnode.add(e2, e1)
                            self.pathnode.set_edge_value(e2, e1, [e2, e1])

                    else:
                        if clearance_from >= 2 and clearance_to >= 2:
                            begin_y = yy

                if begin_y != None:
                    begin = (end_x - 1, begin_y)
                    end = (end_x - 1, yy)
                    e1 = self.insert_entrance_point(begin, end, entrance_point[x, y])

                    begin = (end_x, begin_y)
                    end = (end_x, yy)
                    e2 = self.insert_entrance_point(begin, end, entrance_point[x + 1, y])
                    begin_y = None

                    self.pathnode.add(e1, e2)
                    self.pathnode.set_edge_value(e1, e2, [e1, e2])
                    self.pathnode.add(e2, e1)
                    self.pathnode.set_edge_value(e2, e1, [e2, e1])

                for e in entrance_point[x, y][:]:
                    for e2 in entrance_point[x, y][:]:
                        if e == e2:
                            continue;

                        path = Pathfinder.a_star(e, e2, cluster_pathnode[x, y])

                        if path == False:
                            continue

                        self.pathnode.add(e, e2)
                        self.pathnode.set_edge_value(e, e2, path)


        for node in self.pathnode.list:
            neighbors = self.pathnode.neighbors(node)
            e1 = Vec2d(node) * 16

            self.path_overlay.blit(self.encpath, e1)
            for n in neighbors:
                e2 = Vec2d(n) * 16
                path = self.pathnode.get_edge_value(node, n)
                if path:
                    worldpath = []

                    for p in path:
                        p = (p[0] * pw + pw, p[1] * ph + ph)
                        worldpath.append(p)

                    pygame.draw.lines(self.path_overlay, (255, 255, 0), False, worldpath, 2)

                # else:
                    # pygame.draw.line(self.path_overlay, (255,255,0), e1, e2, 2)

    def generate_path_overlay(self):
        path_overlay = pygame.Surface(self.map_size, pygame.SRCALPHA, 32)

        encpath = pygame.Surface((16, 16), pygame.SRCALPHA, 32)
        encpath.fill(pygame.Color(0, 255, 0, 192))

        for node in self.pathnode.list:
            neighbors = self.pathnode.neighbors(node)
            e1 = Vec2d(node) * 16

            path_overlay.blit(encpath, e1)

            for n in neighbors:
                path = self.pathnode.get_edge_value(node, n)
                if path:
                    worldpath = []

                    for p in path:
                        p = (p[0] * 16, p[1] * 16)
                        worldpath.append(p)

                    pygame.draw.lines(path_overlay, (255, 255, 0), False, worldpath, 2)


        self.path_overlay = path_overlay


    def insert_entrance_point(self, begin, end, saved_list):
        tw = self.tiledmap.tilewidth
        th = self.tiledmap.tileheight
        pw = tw / 2
        ph = th / 2

        mid_x = int((begin[0] + end[0]) / 2)
        mid_y = int((begin[1] + end[1]) / 2)
        mid = (mid_x, mid_y)

        saved_list.append((mid_x, mid_y))
        return mid

    def draw_clearance_tile(self, x, y):
        tw = self.tiledmap.tilewidth
        th = self.tiledmap.tileheight
        pw = tw / 2
        ph = th / 2

        if self.get_clearance((x, y)) < 2:
            self.path_overlay.blit(self.badpath, (x * pw, y * ph))
        else:
            self.path_overlay.blit(self.passpath, (x * pw, y * ph))



    def generate_pathmap_overlay(self):
        # draw pathing map
        tw = self.tiledmap.tilewidth
        th = self.tiledmap.tileheight
        pw = tw / 2
        ph = th / 2


        pathtile = pygame.Surface((pw, ph))
        pathtile.fill(pygame.Color(0, 255, 0))

        blocktile = pygame.Surface((pw, ph))
        blocktile.fill(pygame.Color(64, 0, 0))

        self.pathmap_overlay = pygame.Surface(self.map_size)

        for y in xrange(0, self.tiledmap.height * 2):
            for x in xrange(0, self.tiledmap.width * 2):
                if self.pathmap[x, y]:
                    self.pathmap_overlay.blit(pathtile, (x * pw, y * ph))
                else:
                    self.pathmap_overlay.blit(blocktile, (x * pw, y * ph))

        self.pathmap_overlay.set_alpha(64)

    def generate_grid_overlay(self):
        tw = self.tiledmap.tilewidth
        th = self.tiledmap.tileheight
        pw = tw / 2
        ph = th / 2

        # draw grid
        gridcolor = pygame.Color(96, 96, 96)
        midcolor = pygame.Color(128, 128, 128)

        self.grid_overlay = pygame.Surface(self.map_size, pygame.SRCALPHA, 32)
        for y in xrange(0, self.tiledmap.height * 2):
            if y % 2:
                ycolor = gridcolor
            else:
                ycolor = midcolor

            for x in xrange(0, self.tiledmap.width * 2):
                topright = ((x + 1) * pw, y * ph)
                bottomright = ((x + 1) * pw, (y + 1) * ph)
                bottomleft = ((x) * pw, (y + 1) * ph)

                if x % 2:
                    xcolor = gridcolor
                else:
                    xcolor = midcolor

                pygame.draw.line(self.grid_overlay, xcolor, topright, bottomright)
                pygame.draw.line(self.grid_overlay, ycolor, bottomleft, bottomright)

        """# draw tile id
        font = pygame.font.Font(pygame.font.get_default_font(), 12)
        fontcolor = pygame.Color(0,0,32)

        for y in xrange(0, self.tiledmap.height):
            for x in xrange(0, self.tiledmap.width):

                gid = self.tiledmap.getTileGID(x,y, 0)
                gid_surface = font.render(str(gid), 1, fontcolor)
                self.grid_overlay.blit(gid_surface, (x*tw, y*th))"""

    def generate_clearance_overlay(self):
        tw = self.tiledmap.tilewidth
        th = self.tiledmap.tileheight

        pw = tw / 2
        ph = th / 2
        font = pygame.font.Font(pygame.font.get_default_font(), 12)
        self.clearance_overlay = pygame.Surface(self.map_size, pygame.SRCALPHA, 32)

        for y in xrange(0, self.tiledmap.height * 2):
            for x in xrange(0, self.tiledmap.width * 2):
                c = 0
                if (x, y) in self.clearance:
                    c = self.clearance[x, y]

                clearance_surface = font.render(str(c), 1, (0, 0, 0))
                self.clearance_overlay.blit(clearance_surface, (x * pw, y * ph))

    def render(self, target):
        tw = self.tiledmap.tilewidth
        th = self.tiledmap.tileheight

        self.surface = pygame.Surface(self.map_size)
        for layer in self.layer_surface:
            self.surface.blit(layer, (0, 0))

        if self.render_option.debug:
            # self.surface.blit(self.pathmap_overlay, (0,0))
            #self.surface.blit(self.clearance_overlay, (0,0))

            self.surface.blit(self.grid_overlay, (0, 0))

            # draw scanned path
            scantile = pygame.Surface((tw / 2, th / 2))
            scantile.fill(pygame.Color(0, 0, 255))
            scantile.set_alpha(64)

            offendtile = pygame.Surface((tw / 2, th / 2))
            offendtile.fill(pygame.Color(255, 0, 0))
            offendtile.set_alpha(64)

            if self.closedset:
                for (x, y) in self.closedset:
                    self.surface.blit(scantile, (x * tw / 2, y * th / 2))

            # draw terrain collision
            position = self.player.position
            tx = int(position.x / (self.tiledmap.tilewidth / 2))
            ty = int(position.y / (self.tiledmap.tileheight / 2))

            for x in xrange(tx - 1, tx + 2):
                for y in xrange(ty - 1, ty + 2):
                    self.surface.blit(scantile, (x * tw / 2, y * th / 2))

            if self.map_collide_offender:
                (x, y) = self.map_collide_offender
                self.surface.blit(offendtile, (x * tw / 2, y * th / 2))

            if self.last_get_pathmap:
                for (x, y) in self.last_get_pathmap:
                    self.surface.blit(offendtile, (x * tw / 2, y * th / 2))

        # mid point, use for rendering based on focus point
        self.offset = self.focus - (self.view_port_size / 2)

        # target.blit(self.surface, (-self.offset.x, -self.offset.y))
        return self.surface

class RenderOption(object):
    def __init__(self):
        self.debug = False
        self.show_pathing = False

class PathGraph(object):
    def __init__(self):
        self.list = dict()
        self.node_value = dict()
        self.edge_value = dict()


    def adjacent(self, x, y):
        # tests whether there is an edge from node x to node y.
        if x in self.list:
            if y in self.list[x]:
                return True

        return False

    def neighbors(self, x):
        # lists all nodes y such that there is an edge from x to y.
        if x in self.list:
            return self.list[x]

        else:
            return []

    def add(self, x, y):
        # adds to G the edge from x to y, if it is not there.
        if x not in self.list:
            self.list[x] = []

        self.list[x].append(y)
        self.node_value[x] = None
        self.edge_value[x, y] = None

    def delete(self, x, y):
        # removes the edge from x to y, if it is there.
        if x in self.list:
            if y in self.list[x]:
                self.list[x].remove(y)

        if (x, y) in self.node_value:
            self.node_value.pop((x, y))

        if (x, y) in self.edge_value:
            self.edge_value.pop((x, y))


    def get_node_value(self, x):
        # returns the value associated with the node x
        if x in self.node_value:
            return self.node_value[x]

    def set_node_value(self, x, a):
        # sets the value associated with the node x to a.
        self.node_value[x] = a

    def get_edge_value(self, x, y):
        # returns the value associated to the edge (x,y).
        if (x, y) in self.edge_value:
            return self.edge_value[x, y]

    def set_edge_value(self, x, y, v):
        # sets the value associated to the edge (x,y) to v.
        self.edge_value[x, y] = v


class Pathfinder(object):
    def __init__(self):
        None

    @staticmethod
    def a_star(start, goal, pathnode=None):
        if pathnode == None:
            pathnode = Map.game_map.base_clearance

        """
        # Refill start nodes (Ignore self colision)
        (x, y) = start
        for px in xrange(x - 2, x + 2):
            for py in xrange(y - 2, y + 2):
                if (px, py) in Map.game_map.base_clearance:
                    pathnode[(px, py)] = Map.game_map.base_clearance[(px, py)]
        """
        """
        if pathnode[start] == 0:
            return False

        if pathnode[start] == 1:
            (x,y) = (start[0]-1, start[1]-1)
            if (x,y) in pathnode and pathnode[x,y] >= 2:
                start = (x,y)
        """

        if goal not in pathnode:
            return False

        if pathnode[goal] == 0:
            return False

        if pathnode[goal] == 1:
            (x, y) = (goal[0] - 1, goal[1] - 1)
            if (x, y) in pathnode and pathnode[x, y] >= 2:
                goal = (x, y)

        closedset = []
        openset = [start]
        came_from = dict()

        g_score = dict()
        f_score = dict()

        g_score[start] = 0
        f_score[start] = g_score[start] + Pathfinder.heuristic_cost(start, goal)

        while len(openset) > 0:
            current = Pathfinder.get_current_node(openset, f_score)
            if current == goal:
                return Pathfinder.reconsturct_path(came_from, current)

            openset.remove(current)
            closedset.append(current)

            neighbour = Pathfinder.get_neighbour(current, pathnode)
            for n in neighbour:
                if n in closedset:
                    continue

                distance = Vec2d(current) - n
                distance = distance.get_length() * 16
                tentative_g_score = g_score[current] + 16

                if n not in openset or tentative_g_score <= g_score[n]:
                    came_from[n] = current
                    g_score[n] = tentative_g_score
                    f_score[n] = g_score[n] + Pathfinder.heuristic_cost(n, goal)

                    if n not in openset:
                        openset.append(n)

        return False

    @staticmethod
    def haa_star(start, goal):
        pathnode = Map.game_map.pathnode

        closedset = []
        openset = [start]
        came_from = dict()

        g_score = dict()
        f_score = dict()

        g_score[start] = 0
        f_score[start] = g_score[start] + Pathfinder.heuristic_cost(start, goal)

        while len(openset) > 0:
            current = Pathfinder.get_current_node(openset, f_score)
            if current == goal:
                Map.game_map.closedset = closedset
                return Pathfinder.reconsturct_path(came_from, current)

            openset.remove(current)
            closedset.append(current)

            neighbour = pathnode.neighbors(current)
            for n in neighbour:
                if n in closedset:
                    continue

                distance = Vec2d(current) - n
                distance = distance.get_length() * 16
                tentative_g_score = g_score[current] + 16

                if n not in openset or tentative_g_score <= g_score[n]:
                    came_from[n] = current
                    g_score[n] = tentative_g_score
                    f_score[n] = g_score[n] + Pathfinder.heuristic_cost(n, goal)

                    if n not in openset:
                        openset.append(n)




        Map.game_map.closedset = closedset
        return False

    @staticmethod
    def get_current_node(openset, f_score):
        next_node = None

        for o in openset:
            if next_node == None:
                next_node = o

            elif f_score[o] < f_score[next_node]:
                next_node = o

        return next_node

    @staticmethod
    def get_neighbour(source, pathnode):
        neighbour = []

        x = source[0]
        y = source[1]

        l = r = u = d = False  # Flags for deciding diagonal path

        left = (x - 1, y)
        if left in pathnode and pathnode[left] >= 2:
            neighbour.append(left)
            l = True

        right = (x + 1, y)
        if right in pathnode and pathnode[right] >= 2:
            neighbour.append(right)
            r = True

        up = (x, y - 1)
        if up in pathnode and pathnode[up] >= 2:
            neighbour.append(up)
            u = True

        down = (x, y + 1)
        if down in pathnode and pathnode[down] >= 2:
            neighbour.append((x, y + 1))
            d = True


        if u and l:
            up_left = (x - 1, y - 1)
            if up_left in pathnode and pathnode[up_left] >= 2:
                neighbour.append(up_left)

        if u and r:
            up_right = (x + 1, y - 1)
            if up_right in pathnode and pathnode[up_right] >= 2:
                neighbour.append(up_right)

        if d and l:
            down_left = (x - 1, y + 1)
            if down_left in pathnode and pathnode[down_left] >= 2:
                neighbour.append(down_left)

        if d and r:
            down_right = (x + 1, y + 1)
            if down_right in pathnode and pathnode[down_right] >= 2:
                neighbour.append(down_right)

        return neighbour

    @staticmethod
    def heuristic_cost(source, destination):
        d = Vec2d(destination) - source
        return d.get_length() * 16

    @staticmethod
    def reconsturct_path(came_from, current_node):
        if current_node in came_from:
            p = Pathfinder.reconsturct_path(came_from, came_from[current_node])
            p.append(current_node)
            return p
        else:
            p = [current_node]
            return p

import json
class ResourceManager(object):
    def __init__(self):
        self.images = {}
        self.image_datapath = os.path.join("data", "image")

        self.units = {}
        self.unit_datapath = os.path.join("data", "unit")

    def get_image(self, filename):
        if filename not in self.images:
            filename = os.path.join(self.image_datapath, filename);
            self.images[filename] = pygame.image.load(filename).convert_alpha()

        return self.images[filename]

    def get_unit(self, filename):
        if filename not in self.units:
            filename = os.path.join(self.unit_datapath, filename);
            self.units[filename] = json.load(open(filename, 'r'))

        return self.units[filename]



### vector ###
import operator
import math

class Vec2d(object):
    """2d vector class, supports vector and scalar operators,
       and also provides a bunch of high level functions
       """
    __slots__ = ['x', 'y']

    def __init__(self, x_or_pair, y=None):
        if y == None:
            self.x = x_or_pair[0]
            self.y = x_or_pair[1]
        else:
            self.x = x_or_pair
            self.y = y

    def __len__(self):
        return 2

    def __getitem__(self, key):
        if key == 0:
            return self.x
        elif key == 1:
            return self.y
        else:
            raise IndexError("Invalid subscript " + str(key) + " to Vec2d")

    def __setitem__(self, key, value):
        if key == 0:
            self.x = value
        elif key == 1:
            self.y = value
        else:
            raise IndexError("Invalid subscript " + str(key) + " to Vec2d")

    # String representaion (for debugging)
    def __repr__(self):
        return 'Vec2d(%s, %s)' % (self.x, self.y)

    # Comparison
    def __eq__(self, other):
        if hasattr(other, "__getitem__") and len(other) == 2:
            return self.x == other[0] and self.y == other[1]
        else:
            return False

    def __ne__(self, other):
        if hasattr(other, "__getitem__") and len(other) == 2:
            return self.x != other[0] or self.y != other[1]
        else:
            return True

    def __nonzero__(self):
        return bool(self.x or self.y)

    # Generic operator handlers
    def _o2(self, other, f):
        "Any two-operator operation where the left operand is a Vec2d"
        if isinstance(other, Vec2d):
            return Vec2d(f(self.x, other.x),
                         f(self.y, other.y))
        elif (hasattr(other, "__getitem__")):
            return Vec2d(f(self.x, other[0]),
                         f(self.y, other[1]))
        else:
            return Vec2d(f(self.x, other),
                         f(self.y, other))

    def _r_o2(self, other, f):
        "Any two-operator operation where the right operand is a Vec2d"
        if (hasattr(other, "__getitem__")):
            return Vec2d(f(other[0], self.x),
                         f(other[1], self.y))
        else:
            return Vec2d(f(other, self.x),
                         f(other, self.y))

    def _io(self, other, f):
        "inplace operator"
        if (hasattr(other, "__getitem__")):
            self.x = f(self.x, other[0])
            self.y = f(self.y, other[1])
        else:
            self.x = f(self.x, other)
            self.y = f(self.y, other)
        return self

    # Addition
    def __add__(self, other):
        if isinstance(other, Vec2d):
            return Vec2d(self.x + other.x, self.y + other.y)
        elif hasattr(other, "__getitem__"):
            return Vec2d(self.x + other[0], self.y + other[1])
        else:
            return Vec2d(self.x + other, self.y + other)
    __radd__ = __add__

    def __iadd__(self, other):
        if isinstance(other, Vec2d):
            self.x += other.x
            self.y += other.y
        elif hasattr(other, "__getitem__"):
            self.x += other[0]
            self.y += other[1]
        else:
            self.x += other
            self.y += other
        return self

    # Subtraction
    def __sub__(self, other):
        if isinstance(other, Vec2d):
            return Vec2d(self.x - other.x, self.y - other.y)
        elif (hasattr(other, "__getitem__")):
            return Vec2d(self.x - other[0], self.y - other[1])
        else:
            return Vec2d(self.x - other, self.y - other)
    def __rsub__(self, other):
        if isinstance(other, Vec2d):
            return Vec2d(other.x - self.x, other.y - self.y)
        if (hasattr(other, "__getitem__")):
            return Vec2d(other[0] - self.x, other[1] - self.y)
        else:
            return Vec2d(other - self.x, other - self.y)
    def __isub__(self, other):
        if isinstance(other, Vec2d):
            self.x -= other.x
            self.y -= other.y
        elif (hasattr(other, "__getitem__")):
            self.x -= other[0]
            self.y -= other[1]
        else:
            self.x -= other
            self.y -= other
        return self

    # Multiplication
    def __mul__(self, other):
        if isinstance(other, Vec2d):
            return Vec2d(self.x * other.x, self.y * other.y)
        if (hasattr(other, "__getitem__")):
            return Vec2d(self.x * other[0], self.y * other[1])
        else:
            return Vec2d(self.x * other, self.y * other)
    __rmul__ = __mul__

    def __imul__(self, other):
        if isinstance(other, Vec2d):
            self.x *= other.x
            self.y *= other.y
        elif (hasattr(other, "__getitem__")):
            self.x *= other[0]
            self.y *= other[1]
        else:
            self.x *= other
            self.y *= other
        return self

    # Division
    def __div__(self, other):
        return self._o2(other, operator.div)
    def __rdiv__(self, other):
        return self._r_o2(other, operator.div)
    def __idiv__(self, other):
        return self._io(other, operator.div)

    def __floordiv__(self, other):
        return self._o2(other, operator.floordiv)
    def __rfloordiv__(self, other):
        return self._r_o2(other, operator.floordiv)
    def __ifloordiv__(self, other):
        return self._io(other, operator.floordiv)

    def __truediv__(self, other):
        return self._o2(other, operator.truediv)
    def __rtruediv__(self, other):
        return self._r_o2(other, operator.truediv)
    def __itruediv__(self, other):
        return self._io(other, operator.floordiv)

    # Modulo
    def __mod__(self, other):
        return self._o2(other, operator.mod)
    def __rmod__(self, other):
        return self._r_o2(other, operator.mod)

    def __divmod__(self, other):
        return self._o2(other, operator.divmod)
    def __rdivmod__(self, other):
        return self._r_o2(other, operator.divmod)

    # Exponentation
    def __pow__(self, other):
        return self._o2(other, operator.pow)
    def __rpow__(self, other):
        return self._r_o2(other, operator.pow)

    # Bitwise operators
    def __lshift__(self, other):
        return self._o2(other, operator.lshift)
    def __rlshift__(self, other):
        return self._r_o2(other, operator.lshift)

    def __rshift__(self, other):
        return self._o2(other, operator.rshift)
    def __rrshift__(self, other):
        return self._r_o2(other, operator.rshift)

    def __and__(self, other):
        return self._o2(other, operator.and_)
    __rand__ = __and__

    def __or__(self, other):
        return self._o2(other, operator.or_)
    __ror__ = __or__

    def __xor__(self, other):
        return self._o2(other, operator.xor)
    __rxor__ = __xor__

    # Unary operations
    def __neg__(self):
        return Vec2d(operator.neg(self.x), operator.neg(self.y))

    def __pos__(self):
        return Vec2d(operator.pos(self.x), operator.pos(self.y))

    def __abs__(self):
        return Vec2d(abs(self.x), abs(self.y))

    def __invert__(self):
        return Vec2d(-self.x, -self.y)

    # vectory functions
    def get_length_sqrd(self):
        return self.x ** 2 + self.y ** 2

    def get_length(self):
        return math.sqrt(self.x ** 2 + self.y ** 2)
    def __setlength(self, value):
        length = self.get_length()
        self.x *= value / length
        self.y *= value / length
    length = property(get_length, __setlength, None, "gets or sets the magnitude of the vector")

    def rotate(self, angle_degrees):
        radians = math.radians(angle_degrees)
        cos = math.cos(radians)
        sin = math.sin(radians)
        x = self.x * cos - self.y * sin
        y = self.x * sin + self.y * cos
        self.x = x
        self.y = y

    def rotated(self, angle_degrees):
        radians = math.radians(angle_degrees)
        cos = math.cos(radians)
        sin = math.sin(radians)
        x = self.x * cos - self.y * sin
        y = self.x * sin + self.y * cos
        return Vec2d(x, y)

    def get_angle(self):
        if (self.get_length_sqrd() == 0):
            return 0
        return math.degrees(math.atan2(self.y, self.x))
    def __setangle(self, angle_degrees):
        self.x = self.length
        self.y = 0
        self.rotate(angle_degrees)
    angle = property(get_angle, __setangle, None, "gets or sets the angle of a vector")

    def get_angle_between(self, other):
        cross = self.x * other[1] - self.y * other[0]
        dot = self.x * other[0] + self.y * other[1]
        return math.degrees(math.atan2(cross, dot))

    def normalized(self):
        length = self.length
        if length != 0:
            return self / length
        return Vec2d(self)

    def normalize_return_length(self):
        length = self.length
        if length != 0:
            self.x /= length
            self.y /= length
        return length

    def perpendicular(self):
        return Vec2d(-self.y, self.x)

    def perpendicular_normal(self):
        length = self.length
        if length != 0:
            return Vec2d(-self.y / length, self.x / length)
        return Vec2d(self)

    def dot(self, other):
        return float(self.x * other[0] + self.y * other[1])

    def get_distance(self, other):
        return math.sqrt((self.x - other[0]) ** 2 + (self.y - other[1]) ** 2)

    def get_dist_sqrd(self, other):
        return (self.x - other[0]) ** 2 + (self.y - other[1]) ** 2

    def projection(self, other):
        other_length_sqrd = other[0] * other[0] + other[1] * other[1]
        projected_length_times_other_length = self.dot(other)
        return other * (projected_length_times_other_length / other_length_sqrd)

    def cross(self, other):
        return self.x * other[1] - self.y * other[0]

    def interpolate_to(self, other, range):
        return Vec2d(self.x + (other[0] - self.x) * range, self.y + (other[1] - self.y) * range)

    def convert_to_basis(self, x_vector, y_vector):
        return Vec2d(self.dot(x_vector) / x_vector.get_length_sqrd(), self.dot(y_vector) / y_vector.get_length_sqrd())

    def __getstate__(self):
        return [self.x, self.y]

    def __setstate__(self, dict):
        self.x, self.y = dict

########################################################################
# # Unit Testing                                                       ##
########################################################################
if __name__ == "__main__":

    import unittest
    import pickle

    ####################################################################
    class UnitTestVec2D(unittest.TestCase):

        def setUp(self):
            pass

        def testCreationAndAccess(self):
            v = Vec2d(111, 222)
            self.assert_(v.x == 111 and v.y == 222)
            v.x = 333
            v[1] = 444
            self.assert_(v[0] == 333 and v[1] == 444)

        def testMath(self):
            v = Vec2d(111, 222)
            self.assertEqual(v + 1, Vec2d(112, 223))
            self.assert_(v - 2 == [109, 220])
            self.assert_(v * 3 == (333, 666))
            self.assert_(v / 2.0 == Vec2d(55.5, 111))
            self.assert_(v / 2 == (55.5, 111))
            self.assert_(v ** Vec2d(2, 3) == [12321, 10941048])
            self.assert_(v + [-11, 78] == Vec2d(100, 300))
            self.assert_(v / [10, 2] == [11.1, 111])

        def testReverseMath(self):
            v = Vec2d(111, 222)
            self.assert_(1 + v == Vec2d(112, 223))
            self.assert_(2 - v == [-109, -220])
            self.assert_(3 * v == (333, 666))
            self.assert_([222, 888] / v == [2, 4])
            self.assert_([111, 222] ** Vec2d(2, 3) == [12321, 10941048])
            self.assert_([-11, 78] + v == Vec2d(100, 300))

        def testUnary(self):
            v = Vec2d(111, 222)
            v = -v
            self.assert_(v == [-111, -222])
            v = abs(v)
            self.assert_(v == [111, 222])

        def testLength(self):
            v = Vec2d(3, 4)
            self.assert_(v.length == 5)
            self.assert_(v.get_length_sqrd() == 25)
            self.assert_(v.normalize_return_length() == 5)
            self.assert_(v.length == 1)
            v.length = 5
            self.assert_(v == Vec2d(3, 4))
            v2 = Vec2d(10, -2)
            self.assert_(v.get_distance(v2) == (v - v2).get_length())

        def testAngles(self):
            v = Vec2d(0, 3)
            self.assertEquals(v.angle, 90)
            v2 = Vec2d(v)
            v.rotate(-90)
            self.assertEqual(v.get_angle_between(v2), 90)
            v2.angle -= 90
            self.assertEqual(v.length, v2.length)
            self.assertEquals(v2.angle, 0)
            self.assertEqual(v2, [3, 0])
            self.assert_((v - v2).length > .00001)
            self.assertEqual(v.length, v2.length)
            v2.rotate(300)
            self.assertAlmostEquals(v.get_angle_between(v2), -60)
            v2.rotate(v2.get_angle_between(v))
            angle = v.get_angle_between(v2)
            self.assertAlmostEquals(v.get_angle_between(v2), 0)

        def testHighLevel(self):
            basis0 = Vec2d(5.0, 0)
            basis1 = Vec2d(0, .5)
            v = Vec2d(10, 1)
            self.assert_(v.convert_to_basis(basis0, basis1) == [2, 2])
            self.assert_(v.projection(basis0) == (10, 0))
            self.assert_(basis0.dot(basis1) == 0)

        def testCross(self):
            lhs = Vec2d(1, .5)
            rhs = Vec2d(4, 6)
            self.assert_(lhs.cross(rhs) == 4)

        def testComparison(self):
            int_vec = Vec2d(3, -2)
            flt_vec = Vec2d(3.0, -2.0)
            zero_vec = Vec2d(0, 0)
            self.assert_(int_vec == flt_vec)
            self.assert_(int_vec != zero_vec)
            self.assert_((flt_vec == zero_vec) == False)
            self.assert_((flt_vec != int_vec) == False)
            self.assert_(int_vec == (3, -2))
            self.assert_(int_vec != [0, 0])
            self.assert_(int_vec != 5)
            self.assert_(int_vec != [3, -2, -5])

        def testInplace(self):
            inplace_vec = Vec2d(5, 13)
            inplace_ref = inplace_vec
            inplace_src = Vec2d(inplace_vec)
            inplace_vec *= .5
            inplace_vec += .5
            inplace_vec /= (3, 6)
            inplace_vec += Vec2d(-1, -1)
            self.assertEquals(inplace_vec, inplace_ref)

        def testPickle(self):
            testvec = Vec2d(5, .3)
            testvec_str = pickle.dumps(testvec)
            loaded_vec = pickle.loads(testvec_str)
            self.assertEquals(testvec, loaded_vec)

    ####################################################################
    unittest.main()

    ########################################################################
